package main.leetcode.primary.from001to100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 17.电话号码的字母组合
 *
 * <p>给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 *
 * <p>给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 *
 * <p>示例:
 *
 * <p>输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex17 {
    private static List<String> list = new ArrayList<>();
    //  private static String[] phone = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private static Map<Integer, String> phone =
            new HashMap<Integer, String>() {
                {
                    put(2, "abc");
                    put(3, "def");
                    put(4, "ghi");
                    put(5, "jkl");
                    put(6, "mno");
                    put(7, "pqrs");
                    put(8, "tuv");
                    put(9, "wxyz");
                }
            };

    public static void main(String[] args) {
        System.out.println(letterCombinations("23"));
    }

    public static List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return list;
        backTrack(digits, "", 0);
        return list;
    }

    private static void backTrack(String digits, String letter, int index) {
        if (index == digits.length()) { // 递归到最后一个字母
            list.add(letter);
            return;
        }
        //    String str = phone[digits.charAt(index) - '0' - 2]; // 取得数字对应字符串
        String str = phone.get(digits.charAt(index) - '0');
        for (int i = 0; i < str.length(); i++) backTrack(digits, letter + str.charAt(i), index + 1);
    }
}
